package org.hot100.h234;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;

/**
 * @Author: wjy
 * @Date: 2022/2/11 17:31
 */
public class Solution {

    public static void main(String[] args) {

        ListNode listNode = new ListNode(1);
        ListNode listNode2 = new ListNode(2, listNode);
        ListNode listNode3 = new ListNode(2, listNode2);
        ListNode listNode4 = new ListNode(1, listNode3);

        Solution solution = new Solution();
        System.out.println(solution.isPalindrome2(listNode4));

    }

    /**
     * 栈
     *
     * @param head
     * @return
     */
    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return false;
        }

        ListNode temp = head.next;
        ListNode temp2 = head;
        Stack<Integer> stack = new Stack<>();
        stack.push(head.val);
        int count = 1;

        while (temp != null) {
            stack.push(temp.val);
            count++;
            temp = temp.next;
        }

        while (temp2 != null) {
            if (stack.peek() == temp2.val) {
                stack.pop();
                count--;
            }
            temp2 = temp2.next;
        }

        if (count == 0) {
            return true;
        }

        return false;
    }

    /**
     * 双指针 ＋ 反转链表
     *
     * @param head
     * @return
     */
    public boolean isPalindrome2(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }

        //       慢指针         快指针
        ListNode slow = head, fast = head, reversal = null, next = null;

        // 反转慢指针指向的链表
        while (fast != null && fast.next != null) {
            next = slow.next;
            fast = fast.next.next;
            slow.next = reversal;
            reversal = slow;
            slow = next;
        }

        // 判断 fast 是否指向了 null
        // 如果链表个数为偶数 fast 最后会指向 null
        // 如果链表个数为奇数 fast 最后会指向 最后一个节点
        // 此处判断主要是考虑到链表个数为奇数的情况
        if (fast != null) {
            slow = slow.next;
        }

        while (reversal != null && slow != null) {
            if (reversal.val != slow.val) {
                return false;
            }
            reversal = reversal.next;
            slow = slow.next;
        }

        return true;
    }

}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}